package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.combinationSum2(new int[]{10,1,2,7,6,1,5}, 8));
        System.out.println(s.combinationSum2(new int[]{2,5,2,1,2}, 5));
    }
}


class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        dfs(candidates, 0, target, ans, new LinkedList<>());
        return ans;
    }

    void dfs(int[] candidates, int i, int target, List<List<Integer>> ans, LinkedList<Integer> cur){
        if(target == 0){
            ans.add(new ArrayList<>(cur));
            return;
        }

        if(i == candidates.length){
            return;
        }

        int candidate = candidates[i];
        if(target < candidate){
            return;
        }

        cur.addLast(candidate);
        dfs(candidates, i + 1, target - candidate, ans, cur);
        cur.removeLast();

        i++;
        while(i < candidates.length && candidates[i] == candidates[i - 1]){
            i++;
        }
        dfs(candidates, i, target, ans, cur);
    }
}